package liangtWorkSpace.sort;

/**
 * @ClassName QuickSort
 * @Description : 功能说明
 * @Author : LiangT
 * @Date : 2020/4/16 12:22
 */

import java.util.Arrays;

/**
 * 快速排序算法实现
 */
public class QuickSort {

    /**
     * 快速排序
     *
     * @param arry
     * @param startIndex
     * @param endIndex
     */
    public static void quickSotr(int[] arry, int startIndex, int endIndex) {
        //设置循环停止的位置
        if (startIndex >= endIndex) {
            return;
        }

//        System.out.println(Arrays.toString(arry));
        //获取基数的位置
        int pivotIndex = partitionOnly(arry, startIndex, endIndex);

        //根据基数的位置，分为两部分进行递归
        quickSotr(arry, startIndex, pivotIndex - 1);
        quickSotr(arry, pivotIndex + 1, endIndex);
    }

    /**
     * 分治双边循环法
     *
     * @param arry      待交换的数组
     * @param starIndex 起始下标
     * @param endIndex  结束下标
     * @return
     */
    public static int partition(int[] arry, int starIndex, int endIndex) {
        int pivot = arry[starIndex];
        int left = starIndex;
        int right = endIndex;
        //交换值
        while (left != right) {
            //获取右节点下标
            while (left < right && arry[right] > pivot) {
                right--;
            }

            //获取左节点下标
            while (left < right && arry[left] <= pivot) {
                left++;
            }
            if (left < right) {
                int p = arry[left];
                arry[left] = arry[right];
                arry[right] = p;
            }
        }
        arry[starIndex] = arry[left];
        arry[left] = pivot;
        return left;
    }

    /**
     * 单边循环
     *
     * @param arry
     * @param startIndex
     * @param endIndex
     * @return
     */
    private static int partitionOnly(int[] arry, int startIndex, int endIndex) {
        int pivot = arry[startIndex];
        int mark = startIndex;
        System.out.println(pivot+"mark:"+mark);
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arry[i] < pivot) {
                mark++;
                int p = arry[mark];
                arry[mark] = arry[i];
                arry[i] = p;
            }
            System.out.println("循环"+Arrays.toString(arry));
        }
        arry[startIndex] = arry[mark];
        arry[mark] = pivot;
        System.out.println("mark="+mark+"单边"+Arrays.toString(arry));
        return mark;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 4, 6, 5, 3, 2, 8, 1};
        quickSotr(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
